package 机试题16年;

import java.util.Arrays;

/**
 * Created by hest0 on 2017/4/19.
 */
public class 股票交易日4 {
    public static void main(String[] args) {
        int[] a = {10, 22, 5, 75, 65, 80};
        int maxProfit = new Stock().maxProfit(a, a.length);
        System.out.println(maxProfit);
    }

    public static class Stock {
        public int maxProfit(int[] prices, int n) {
            // 第i天前的最大利润
            int[] preMaxProfit = new int[n];
            // 第i天后的最大利润
            int[] afterMaxProfit = new int[n];
            // 总利润
            int maxProfit = Integer.MIN_VALUE;

            /**
             *从前往后找最大利润=当前-前面的最小买入
             */
            int minBuy = prices[0];
            for (int i = 1; i < n; i++) {
                preMaxProfit[i] = Math.max(preMaxProfit[i - 1], prices[i] - Math.min(minBuy, prices[i]));
            }
            System.out.println(Arrays.toString(preMaxProfit));

            /**
             *从后往前找最大利润=后面的最大的卖出-当前
             */
            int maxSell = prices[n - 1];
            for (int i = n - 2; i >= 0; i--) {
                afterMaxProfit[i] = Math.max(afterMaxProfit[i + 1], Math.max(maxSell, prices[i]) - prices[i]);
            }
            System.out.println(Arrays.toString(afterMaxProfit));

            /**
             *合成两次动态规划的结果
             */
            for (int i = 0; i < n; i++) {
                maxProfit = Math.max(maxProfit, preMaxProfit[i] + afterMaxProfit[i]);
            }
            return maxProfit;
        }
    }
}


